package 机试题16年;

/**
 * Created by hest0 on 2017/4/19.
 */
public class 字符串交错组成 {
    public static void main(String[] args) {

    }


    public class Mixture {
        public boolean chkMixture(String A, int n, String B, int m, String C, int v) {

            if (n + m != v) return false;

            boolean[][] dp = new boolean[n + 1][m + 1];
            dp[0][0] = true;

            for (int i = 1; i <= m; i++) {
                if (B.charAt(i - 1) == C.charAt(i - 1))
                    dp[0][i] = true;
                else
                    break;
            }

            for (int i = 1; i <= n; i++) {
                if (A.charAt(i - 1) == C.charAt(i - 1))
                    dp[i][0] = true;
                else
                    break;
            }

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] = (dp[i - 1][j] && A.charAt(i - 1) == C.charAt(i + j - 1)) ? true : dp[i][j];
                    dp[i][j] = (dp[i][j - 1] && B.charAt(j - 1) == C.charAt(i + j - 1)) ? true : dp[i][j];
                }
            }

            return dp[n][m];
        }
    }

}
